#include "minheap.h"
#include "printf.h"
#include "stdlib.h"
#include "stdbool.h"

/// @brief 创建最小堆
/// @param capacity 最小堆的容量 
/// @return MinHeap* 最小堆的指针
MinHeap* createMinHeap(int capacity) {
  MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
  if (heap == NULL) {
    printf("最小堆的内存分配失败\n");
    return NULL;
  }
  heap->index = (int*)malloc(sizeof(int) * capacity);
  if (heap->index == NULL) {
    free(heap);
    printf("最小堆的index数组的内存分配失败\n");
    return NULL;
  }
  heap->reverse = (int*)malloc(sizeof(int) * capacity);
  if (heap->reverse == NULL) {
    free(heap->index);
    free(heap);
    printf("最小堆的reverse数组的内存分配失败\n");
    return NULL;
  }
  heap->size = 0;
  heap->capacity = capacity;
  return heap;
}
/// @brief 将元素插入到最小堆中
/// @param heap 最小堆
/// @param dist 存储元素的原数组
/// @param v 要插入的元素在原数组中的索引
/// @return true 插入成功
bool insertIndex(MinHeap* heap, int dist[], int v) {
  if (heap->size == heap->capacity) {
    printf("最小堆已满\n");
    return false;
  }
  int element = dist[v];     // 要插入的元素的值
  int child = heap->size++;  // 要插入的元素在堆中的位置
  while (child > 0) {
    int parent = (child - 1) / 2;
    int parentElement = dist[heap->index[parent]];
    if (parentElement <= element) break;
    heap->index[child] = heap->index[parent];
    heap->reverse[heap->index[child]] = child;
    child = parent;
  }
  heap->index[child] = v;
  heap->reverse[v] = child;
  return true;
}

/// @brief 更新最小堆中的元素(改小)
/// @param heap 最小堆
/// @param dist 存储元素的原数组
/// @param i   要更新的元素在原数组中的索引
/// @param element 更新后的元素值
void fix_up(MinHeap* heap, int dist[], int i, int element) {
  dist[i] = element;  // 更新原数组
  int child = heap->reverse[i];
  while (child > 0) {
    int parent = (child - 1) / 2;
    int parentElement = dist[heap->index[parent]];
    if (parentElement <= element) break;
    heap->index[child] = heap->index[parent];
    heap->reverse[heap->index[child]] = child;
    child = parent;
  }
  heap->index[child] = i;
  heap->reverse[i] = child;
}

/// @brief 删除最小堆的堆顶元素(最小元素)
/// @param heap 最小堆
/// @param dist 存储元素的原数组
/// @return 被删除的元素的索引，如果堆为空，返回-1
/// @note 完全看不懂，由copilot生成
int deleteMin(MinHeap* heap, int dist[]) {
  // 如果堆为空，打印错误信息并返回-1
  if (heap->size == 0) {
    printf("最小堆为空\n");
    return -1;
  }
  // 获取堆顶元素的索引和值
  int minIndex = heap->index[0];
  int minElement = dist[minIndex];
  // 将堆的最后一个元素移动到堆顶
  heap->index[0] = heap->index[--heap->size];
  int parent = 0;
  // 开始下滤操作
  while (parent * 2 + 1 < heap->size) {
    int child = parent * 2 + 1;
    // 如果有右子节点，并且右子节点的值小于左子节点的值，那么将child设置为右子节点的索引
    if (child != heap->size - 1 && dist[heap->index[child]] > dist[heap->index[child + 1]])
      child++;
    // 如果父节点的值小于或等于子节点的值，那么结束下滤操作
    if (dist[heap->index[parent]] <= dist[heap->index[child]]) break;
    // 交换父节点和子节点的位置
    int temp = heap->index[parent];
    heap->index[parent] = heap->index[child];
    heap->reverse[heap->index[parent]] = parent;
    heap->index[child] = temp;
    heap->reverse[temp] = child;
    // 将父节点的索引设置为子节点的索引，继续下滤操作
    parent = child;
  }
  // 返回被删除的元素的索引
  return minIndex;
}
/// @brief 释放最小堆的内存
/// @param heap
void deleteMinHeap(MinHeap* heap) {
  free(heap->index);
  free(heap->reverse);
  free(heap);
}
